package com.ryujung.array.leetCode_406;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/*
Suppose you have a random list of people standing in a queue. Each person is described by  
a pair of integers (h, k), where h is the height of the person and k is the number of people 
in front of this person who have a height greater than or equal to h. Write an algorithm to 
reconstruct the queue.
Note:
The number of people is less than 1,100.

Example
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

思路:
1.排序.第一位代表身高,第二位代表队列前面不小于该高度的人数.
将所有人按照身高降序排列,身高相同,根据人数升序排列.
2.利用ArrayList的add(int,E)的重复索引下添加元素的特性,将排列的数组按顺序存放进去.
3.再将list重新转化为二维数组
*/
public class Solution {
    public static int[][] reconstructQueue(int[][] people) {
        // 根据身高降序排列或者k值升序
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        System.out.println(people);
        //利用AL的add方法特新:同一个位置添加元素会将原有元素向右移动,
        //这里根据k值作为索引下标进行添加即可,由于身高降序,同一个下标的会将高的右移,矮的放左边,
        //即正确的排序方式
        ArrayList<int[]> al = new ArrayList<>();
        for (int[] p : people) {
            al.add(p[1], p);
        }
        return al.toArray(new int[al.size()][2]);
    }

     public static int[][] reconstructQueue2(int[][] people) {
        // 根据身高降序排列或者k值升序
        Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        //利用AL的add方法特新:同一个位置添加元素会将原有元素向右移动,
        //这里根据k值作为索引下标进行添加即可,由于身高降序,同一个下标的会将高的右移,矮的放左边,即正确的排序方式
        LinkedList<int[]> al = new LinkedList<>();
        for (int[] p : people) {//遍历二维数组
            System.out.println("添加的索引是p[1]:"+p[1]);
            al.add(p[1], p); //以p[1],也就是k值作为索引,存到list中
        }
        return al.toArray(new int[al.size()][2]);
    }

    public static void main(String[] args) {
        int[][] people = new int[][] { { 7, 0 }, { 4, 4 }, { 7, 1 }, { 5, 0 }, { 6, 1 }, { 5, 2 } };
        int[][] res = reconstructQueue2(people);
        for (int[] r : res) {
            System.out.println(r[0] + ":" + r[1]);
        }

        //演示al的add(int,E)方法的特点:自动将原有值右移
        LinkedList<String> al = new LinkedList<>();
        al.add(0,"a");
        al.add(0,"b");
        al.add(2,"c");
        al.add(1,"d");
        //该方法存在索引越界异常的可能

        System.out.println(al);
    }
}